/**
 * LeetCode 14. 最长公共前缀
 */
public class Solution_14 {
    /**
     * 方法二：纵向扫描
     * <p>
     * 从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同
     * <p>
     * 时间复杂度：O(s)，s 为所有字符串长度之和
     * <p>
     * 空间复杂度：O(1)
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String ans = strs[0];
        int len = strs[0].length();
        // 遍历所有字符串的每一列
        for (int i = 0; i < len; i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                // 如果已到达某个字符串的末尾，或者某个字符串的字符出现不匹配
                if (i == strs[j].length() || strs[j].charAt(i) != ch) {
                    return ans.substring(0, i);
                }
            }
        }
        return ans;
    }

    /**
     * 方法一：横向扫描
     * <p>
     * 两两比较，最后结果即为最长公共前缀
     * <p>
     * 时间复杂度：O(s)，s 为所有字符串长度之和
     * <p>
     * 空间复杂度：O(1)
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String ans = strs[0];
        // 遍历字符串数组中的每个字符串
        for (int i = 1; i < strs.length; i++) {
            // 将当前字符串与 ans 进行比较，找出公共前缀
            int j = 0;
            while (j < ans.length() && j < strs[i].length() && ans.charAt(j) == strs[i].charAt(j)) {
                j++;
            }
            ans = ans.substring(0, j);
            // 不存在公共前缀，直接返回
            if ("".equals(ans)) {
                return ans;
            }
        }
        return ans;
    }
}
